Data compression techniques aim to enable information to be represented as accurately as possible with a reduced amount of data (i.e., fewer bits compared to the original data). By reducing the number of bits required to be transmitted and stored by information transmission/storage systems, data compression techniques greatly reduce memory size and bandwidth (i.e., bus widths, etc.) requirements of such systems. Additionally, information recovery speed can be increased. There are many types of data compression techniques. Broadly, all data compression techniques fall into one of two categories: lossless (i.e., information preserving) and lossy. Lossy techniques can reproduce the original only imperfectly, but the loss in accuracy of reproduction may be made quite small.
One class of data compression techniques which can be used for both lossy and lossless compression implements a mathematical transform to translate a time-domain input signal to the frequency domain, thus revealing the signal's spectral components from the known temporal components. In implementing the transform, filters commonly are employed to break down the input signal into multiple frequency bands, each band having at least a portion of the information needed to reconstruct the input signal. Most approaches then remove redundant and unneeded data present among the multiple frequency bands. Various transformers are employed, depending on factors such as the type of signal being compressed, the amount of compression needed, the available processing capability and the required reproduction fidelity.
A well-known basic time/frequency transform called Fourier Transform (FT), uses orthonormal basis functions of sine and cosine waveform to provide a frequency domain representation of a time domain function. The FT technique is not well-suited for lossless video or image compression, though. Because the basis sine and cosine signals are boundless (they ideally extend infinitely in each direction), the FT works under the assumption that the original time-domain function is periodic in nature. The FT, as a result, does not accurately translate functions having transient components localized in time (i.e., signals, such as video signals, having sharp transitions). This is so because the FT frequency domain spectrum does not explicitly show the time localization of frequency components of an input function, necessary for efficient compression of input functions having transients.
While such a time localization can be obtained by suitably pre-windowing an input signal, as is done in Short-Time FT (STFT), an inherent limitation in the STFT results in a time resolution/frequency resolution tradeoff and poor discretized breakdown and reconstruction of input signals. The Gabor expansion to the STFT enables improved discretized breakdown and reconstruction of signals by using basis signals that are well localized and concentrated in time and frequency, but requires use of accurate, multi-tap, expensive filters to produce the FT frequency plot.
Discrete Cosine Transform (DCT) compression schemes, commonly used with JPEG, MPEG and H.261 video formats, do not correlate well to the broad-band nature of video images due to the use of sinusoidal reference (basis) signals. In addition, DCT compression schemes require an image to be broken down into sub-blocks for filtering and suffer from image degradation at high compression ratios due to block artifacts ("the block effect"). Other compression techniques, such as those utilizing Gaussian and Laplacian transforms, while able to yield considerable compression due to the removal of substantial redundancies among frequency sub-bands, cannot very accurately reproduce the original signal also due to such drawbacks as the "block effect". Such techniques, therefore, also are not well-suited for lossless video or image compression applications which are the principal application of the present invention.
Recently, the use of wavelet transforms has received considerable attention because, by contrast with the aforementioned techniques, their properties make them well-suited for lossless video and image compression applications. Due at least in part to the bound nature of the reference wavelet basis, as well as to the orthoganality of the wavelet basis at different frequency scales, near-perfect reconstruction of a compressed video signal can be achieved. In addition, relatively simple and compact filter banks can be constructed to implement the ("near perfect") wavelet-based decomposition/reconstruction.
Typically, during wavelet-based decomposition, a frequency band of an image signal is decomposed into a number of sub-bands by a bank of bandpass filters. Each sub-band then is translated to a lower frequency band (baseband, for example) by decimating (down-sampling) it and thereafter encoding it. During reconstruction, each encoded sub-band is decoded and then interpolated (up-sampled) back to its original frequency band. The bands then are summed to provide a replica of the original image signal.
The Mallat version of the wavelet transform enables two-dimensional decomposition/reconstruction. Due to the recursive (to achieve the multi-sub-band plot) nature of the wavelet transform, however, a considerable amount of buffer memory may be required to store temporarily information in the filter pipeline. Additionally, due to the mathematical properties of the wavelet basis and transform, most prior art approaches to wavelet-based video image compression have been implemented in software.
It is a general object of the present invention to provide a simple, yet accurate, lossless wavelet-based video image compression technique that requires a minimal amount of buffer memory and is implementable in hardware, preferably on a single monolithic substrate.